package zwp.exercise.intereview.base.sort.QuickSort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/28 19:33
 * @description 双边循环 - 不稳定
 */
public class QuickSort2 {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println(Arrays.toString(array));
        recursion(array, 0, array.length - 1);
    }

    /**
     * 递归
     * @param array 数组
     * @param l 左边界
     * @param r 右边界
     */
    private static void recursion(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        // 调用排序
        int partition = partition(array, l, r);
        // 左边分区排序
        recursion(array, l, partition - 1);
        //右边分区排序
        recursion(array, partition + 1, r);
    }

    /**
     * 排序
     * @param array 数组
     * @param l 左边界
     * @param r 右边界
     * @return 索引
     */
    private static int partition(int[] array, int l, int r) {
        //标记基准点i,决定了先从j开始向左查找
        int i = l;
        int j = r;
        //基准点值
        int value = array[l];
        //循环-遵循铁的原则:基准点不能变!
        while (i < j) {
            //i < j避免索引不重叠(i=j)当,i=j时推出循环,从右找,先查找小的
            while (i < j && array[j] > value) {
                j--;
            }
            //array[i] <= value排除 value本身,避免基准点元素被交换走,从左找,找大的
            while (i < j && array[i] <= value) {
                i++;
            }
            //重叠后交换
            exchange(array, i, j);
        }
        //分区排序,分区值交换
        exchange(array, l, j);
        System.out.println(Arrays.toString(array));
        //返回重叠索引
        return j;
    }

    private static void exchange(int[] array, int l, int r) {
        int temp = array[l];
        array[l] = array[r];
        array[r] = temp;
    }
}
